package com.LeetCode.String;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 中文敏感词过滤
 * 因为中文字符有很多，一个几万位是数组是十分浪费空间的，所以我打算采用 HashMap 的方式存储中文字符
 */
public class ACAutoMatchCN {

    /**
     * 提前构造好替换的字符串
     */
    String[] fits = {"", "*", "**", "***", "****", "*****",
            "******", "*******", "********", "*********",
            "**********", "***********", "************", "*************",
            "**************", "***************", "****************", "*****************",
            "******************", "*******************", "********************",
            "*********************", "**********************", "***********************", "" +
            "************************", "*************************", "**************************",
            "***************************", "****************************", "*****************************",
            "******************************", "*******************************",
            "********************************",};

    private class ACNode{
        char data; // 存放的字符
        Map<Character, ACNode> children = new HashMap<>();//子节点
        boolean isEnd = false;
        int len ;
        ACNode fail; // 失败指针
        public ACNode(char data){
            this.data = data;
        }
    }

    ACNode root;

    public ACAutoMatchCN(String[] strs){
        root = new ACNode('/');
        for(String str: strs){
            InitInsert(str);
        }

        buildFailNode();
    }

    public void InitInsert(String str){
        ACNode cur = root;
        char[] chars = str.toCharArray();
        for(int i = 0; i<chars.length; i++){
            if(cur.children.get(chars[i]) == null){
                cur.children.put(chars[i], new ACNode(chars[i]));
            }
            cur = cur.children.get(chars[i]);
        }
        cur.isEnd = true;
        cur.len = chars.length;
    }

    public void insert(String str){
        ACNode cur = root;
        char[] chars = str.toCharArray();
        for(int i = 0; i<chars.length; i++){
            if(cur.children.get(chars[i]) == null){
                cur.children.put(chars[i], new ACNode(chars[i]));
            }
            cur = cur.children.get(chars[i]);
        }
        cur.isEnd = true;
        cur.len = chars.length;

        //重新维护失败指针
        buildFailNode();
    }


    public void buildFailNode(){
        Queue<ACNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            ACNode cur = queue.poll();
            for(Character c : cur.children.keySet()){
                ACNode cur_child = cur.children.get(c);
                if(cur_child == null) continue;
                if(cur == root){
                    cur_child.fail = root;
                }else{
                    ACNode cur_fail = cur.fail;
                    while(cur_fail != null){
                        ACNode cur_fail_child = cur.fail.children.get(c);
                        if(cur_fail_child != null){
                            cur_child.fail = cur_fail_child;
                            break;
                        }
                        cur_fail = cur_fail.fail;
                    }
                    if(cur_fail == null){
                        cur_child.fail = root;
                    }
                }
                queue.offer(cur_child);
            }
        }
    }

    /**
     * 过滤敏感词
     * @param str 用户输入的文本
     * @return
     */
    public String filterStr(String str){
        char[] chars = str.toCharArray();
        int len = chars.length;
        ACNode cur = root;
        StringBuilder strb = new StringBuilder();
        for(int i = 0; i<len; i++){
            char c = chars[i];

            while(cur.children.get(c) == null && cur != root){
                cur = cur.fail;
            }

            strb.append(c);
            if(cur.children.get(c) != null){

                //回退已经构造好的字符，并替换为 * 号
                if(cur.children.get(c).isEnd){
                    strb.delete(strb.length() - cur.children.get(c).len  , strb.length());
                    strb.append(fits[cur.children.get(c).len]);
                }

//                System.out.println(cur.children.get(c).data
//                        + " " + cur.children.get(c).isEnd
//                        + " "+ cur.children.get(c).len);
                cur = cur.children.get(c);
            }
        }
        return strb.toString();
    }


    public static void main(String[] args) {
        String[] BadWordSet = {"屌","你秀你妈呢","你妈死了","你妈炸了","去操你自己吧!","nmsl","wdnmd"};
        String FuckText = "屌屌屌，我我屌我爱你屌呀，你也爱我呀，我我屌你妈啊，哈哈哈哈，我去你秀你妈呢" +
                "，你妈死了你妈死了我tm的，屌你妈炸了吧啊,dskfnjgnmslnjfkdbg,njalkgndwdnmd那就danjsklfn";
        ACAutoMatchCN acAutoMatchCN = new ACAutoMatchCN(BadWordSet);
        System.out.println(FuckText);
        System.out.println(acAutoMatchCN.filterStr(FuckText));
    }

    @Test
    public void test(){

    }
}
